n,m,l,r = map(int,input().split())
prices = []
for _ in range(m):
    prices.append(tuple(input().split()))

# 定义邻接矩阵
inf = float('inf')
distance = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n+1):
    distance[i][i] = 0

for start,end,cost in prices:
    distance[int(start)][int(end)] = int(cost)
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if distance[i][j] != inf and distance[i][k] != inf and distance[k][j]!=inf:
                distance[i][j] = max((distance[i][k],distance[k][j],distance[i][j]))
            else:
                distance[i][j] = max(distance[i][k],distance[k][j])

print()